package C034;

/**
 * ClassName: C06_Sort
 * Package: C034
 * Description:
 *
 * @Author BCXJ
 * @Create 2025/1/6 17:12
 * @Version 1.0
 * @Since 1.0
 */
public class C06_Sort {
    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(3);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(1);
        ListNode listNode4 = new ListNode(4);
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;

        ListNode listNode = sortList(listNode1);
        while (listNode != null) {
            System.out.println(listNode.val);
            listNode = listNode.next;
        }
    }


    // 不要提交这个类
    public static class ListNode {
        public int val;
        public ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }


    public static ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        // 链表的长度n
        int n = 0;
        ListNode cur = head;
        while (cur != null) {
            cur = cur.next;
            n++;
        }

        // 非递归的归并排序
        ListNode l1, r1, l2, r2, next, preTeamEnd;
        for (int i = 1; i < n; i <<= 1) {
            // 第一个整合需要特殊记录，把头结点记录下来
            l1 = head;
            r1 = findEnd(l1, i);
            l2 = r1.next;
            r2 = findEnd(l2, i);
            next = r2.next;
            r1.next = null;
            r2.next = null;
            merge(l1, r1, l2, r2);
            head = start;
            preTeamEnd = end;
            while(next != null) {
                l1 = next;
                r1 = findEnd(l1, i);
                l2 = r1.next;
                if(l2 == null) {
                    preTeamEnd.next = l1;
                    break;
                }
                r2 = findEnd(l2, i);
                next = r2.next;
                r1.next = null;
                r2.next = null;
                merge(l1, r1, l2, r2);
                preTeamEnd.next = start;
                preTeamEnd = end;
            }
        }

        return head;

    }

    public static ListNode start = null;
    public static ListNode end = null;

    /**
     * 合并待排序的链表, 确保稳定性
     */
    private static void merge(ListNode l1, ListNode r1, ListNode l2, ListNode r2) {
        ListNode pre = null;
        if (l1.val <= l2.val) {
            start = l1;
            pre = l1;
            l1 = l1.next;
        } else {
            start = l2;
            pre = l2;
            l2 = l2.next;
        }

        // 归并排序
        while(l1 != null && l2 != null) {
            if(l1.val <= l2.val) {
                pre.next = l1;
                pre = l1;
                l1 = l1.next;
            }else {
                pre.next = l2;
                pre = l2;
                l2 = l2.next;
            }
        }

        // 整合剩下的部分
        if(l1 != null) {
            pre.next = l1;
            pre = l1;
            l1 = l1.next;
            end = r1;
        }

        if(l2 != null) {
            pre.next = l2;
            pre = l2;
            l2 = l2.next;
            end = r2;
        }

    }


    // 找出链表l1 开头的后面的k个节点
    private static ListNode findEnd(ListNode head, int i) {
        while (head.next != null && --i > 0) {
            head = head.next;
        }
        return head;
    }
}
